<?php

// A number study:
// Write a function that takes an unsigned integer and returns the number of ’1′ bits it has.

// Two's compliment: -x == ~x+1

$num = 123456;
echo $num . " is " . decbin($num);
echo " has " . getOneBitNumAwesome($num) . " bits of 1s.";

// Solution 1: O(lg n)
function getOneBitNum( $num ){
	$count = 0;
	while( $num > 0 ){
		$count += $num % 2;
		$num = floor( $num / 2 );
	}
	return $count;
}

// Solution 2: O(m) where m is number of 1 bits.
// 0 == x & (x-1) can be used to judge is a number is power of 2.
// Trick: what is x' if x' = x & (x-1)?
// It's the remainder of the number after minusing the least significant power of 2 component of the number:
// 1001000 & (1001000 - 1) = 1001000 & 1000111 = 100000
// It is also called to be "turning off right most '1' bit"
function getOneBitNumAwesome( $num ){
	$count = 0;
	while( $num ){
		$num = $num & ($num - 1);
		$count++;
	}
	return $count;
}